A multiplier method with automatic limitation of penalty growth

This paper presents a multiplier method for solving optimization problems with equality and inequality constraints. The method realizes all the good features that were foreseen by R. Fletcher for this type of algorithm in the past, but which suffers from none of the drawbacks of the earlier attempts.Research sponsored by the National Science Foundation (RANN) Grant ENV76-04264 the National Science Foundation Grant ENG73-08214-A01 and the Sweden-American Foundation.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.     

Linear phase transition in random linear constraint satisfaction problems

Our model is a generalized linear programming relaxation of a much studied random K-SAT problem. Specifically, a set of linear constraints on K variables is fixed. From a pool of n variables, K variables are chosen uniformly at random and a constraint is chosen from also uniformly at random. This procedure is repeated m times independently. We are interested in whether the resulting linear programming problem is feasible. We prove that the feasibility property experiences a linear phase transition, when n and m = cn for a constant c. Namely, there exists a critical value c^* such that, when c < c^*, the problem is feasible or is asymptotically almost feasible, as n, but, when c>c^*, the distance to feasibility is at least a positive constant independent of n. Our result is obtained using the combination of a powerful local weak convergence method developed in Aldous [Ald92], [Ald01], Aldous and Steele [AS03], Steele [Ste02] and martingale techniques. By exploiting a linear programming duality, our theorem implies the following result in the context of sparse random graphs G(n, cn) on n nodes with cn edges, where edges are equipped with randomly generated weights. Let (n, c) denote maximum weight matching in G(n, cn). We prove that when c is a constant and n , the limit lim_n (n, c)/n, exists, with high probability. We further extend this result to maximum weight b-matchings also in G(n, cn).     

Fully Invariant Subgroups of Abelian p-Groups with Finite Ulm–Kaplansky Invariants

We study primary groups containing proper fully invariant subgroups isomorphie to the group. The admissable sequence of Ulm–Kaplansky invariants for primary groups is introduced. Using these sequences, If-groups are described in the classes of seperable and periodically complete groups.     

A unified method for a class of convex separable nonlinear knapsack problems

In this paper, a unified algorithm is proposed for solving a class of convex separable nonlinear knapsack problems, which are characterized by positive marginal cost (PMC) and increasing marginal loss–cost ratio (IMLCR). By taking advantage of these two characteristics, the proposed algorithm is applicable to the problem with equality or inequality constraints. In contrast to the methods based on Karush–Kuhn–Tucker (KKT) conditions, our approach has linear computation complexity. Numerical results are reported to demonstrate the efficacy of the proposed algorithm for different problems.     

A facility location and installation of resources model for level of repair analysis

The Level of Repair Analysis – LORA – is an analytic methodology aimed at determining: (i) the optimal location of facilities that compose a maintenance structure; (ii) the quantity of required resources in each facility; and (iii) the best repair policies, i.e., rules that determine if a given component should be discarded or repaired, and where those actions should take place. This work presents a mixed-integer programming model for LORA that is more comprehensive than others in the literature, being suitable to many practical situations. The model was applied to 15 substantial real world problems, and considering distinct maintenance policies to some of them, resulted in 22 different solutions, all of which could be achieved by a commercial Mixed-Integer Programming (MIP) solver in reasonable times.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

Two-stage integer programs with stochastic right-hand sides: a superadditive dual approach

We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature. This work is supported by National Science Foundation grants DMI-0217190 and DMI-0355433.     

长周期光纤光栅的功率特性

用Matlab编程的方法对长周期光栅功率特性进行了研究,数值模拟了长周期光栅入射角度、光栅长度与功率分布的图像关系.研究结论为长周期光纤光栅的设计提供理论依据.